\documentclass[12pt, a4paper]{article}
\usepackage{geometry}
\geometry{
	a4paper,
	left=12.7 mm,
	right=12.7 mm,
	top=12.7 mm,
	bottom=12.7 mm,
}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{physics}
\graphicspath{ {./} }
\usepackage{ctex}

\newcommand{\bvec}[1]{\ensuremath{\mathbf{#1}}}
\newcommand{\matrx}[1]
{
	\ensuremath
	{
		\left (
		\begin{matrix}
			#1
		\end{matrix}
		\right)
	}
}
\newcommand{\formula}[1]{\text{式} \ref{#1} }
\usepackage{comment}

\begin{document}
	\section{离散Fourier变换 (DFT)}
    \footnote{参考：Sauer《数值分析》。使用了AI辅助}
	假设我们已知一个函数$y=f(x)$在区域$x \in [0, L]$内$n$个等距点处的离散值，
	比如 $(x_0,y_0),(x_1,y_1),(x_2,y_2),...,(x_{n-1},y_{n-1})$，且$x, y$都是实数。
	显然，$x_j = \frac{j}{n}L, j=0,1,2,...,n-1$。
	现在我们要求这个函数的Fourier级数。

	我们首先设
	\begin{equation} \label{eq:DCT}
		c_j = \frac{1}{\sqrt{n}} \sum_{k=0}^{n-1} y_k e^{-i\frac{2\pi}{n} j k}
	\end{equation}
	其中$c_k=a_k+ib_k$是一个复数。或许好奇为什么如此设题，我们接下来分析。那么他的逆变换是
	\begin{equation}
		y_j = \frac{1}{\sqrt{n}} \sum_{k=0}^{n-1} c_k e^{i\frac{2\pi}{n} j k}
	\end{equation}
	进一步地推导：
	\begin{equation}\label{eq:3}
		\begin{aligned}
			y_j &= \frac{1}{\sqrt{n}} \sum_{k=0}^{n-1} c_k e^{i\frac{2\pi}{n} j k} \\ 
			&= \frac{1}{\sqrt{n}} \sum_{k=0}^{n-1} c_k e^{i\frac{2\pi k}{L} x_j} \qquad x_j = \frac{j}{n}L\\ 
			&= \frac{1}{\sqrt{n}} \sum_{k=0}^{n-1} (a_k+ib_k) \left(\cos(\frac{2\pi k}{L} x_j) + i\sin(\frac{2\pi k}{L} x_j)\right) \\ 
			&= \frac{1}{\sqrt{n}} \sum_{k=0}^{n-1} \left(a_k\cos(\frac{2\pi k}{L} x_j) - b_k \sin(\frac{2\pi k}{L} x_j)\right) \qquad \text{$y$是实数} \\
		\end{aligned}
	\end{equation}
	我们非常神奇地发现，这个等式非常类似我们之前所说的Fourier级数，我们先前定义的$c_k=a_k+ib_k$类似于相应三角函数的系数。
	在“传统的”Fourier级数中我们得通过复杂的积分找出$a_k, b_k$，而如今我们发现其实只需要做一步矩阵乘法（\formula{eq:DCT}），学名离散Fourier变换（DFT）。

	此外，计算\formula{eq:DCT}时有一个著名的算法叫做快速Fourier变换（FFT），其能大幅减少计算所需时间。
	FFT被称为“二十世纪最伟大的算法”之一。
	
	%并且\formula{eq:3}还有优化余地：我们可以证明
	%\begin{equation}
	%	\cos(\frac{2\pi k}{L} (L/2+\Delta x))=\cos(\frac{2\pi k}{L} (L/2-\Delta x)) 
	%	\qquad
	%	\sin(\frac{2\pi k}{L} (L/2+\Delta x))=-\sin(\frac{2\pi k}{L} (L/2-\Delta x))  
	%\end{equation}
	%这种对称性可以帮助我们省掉一半左右的三角运算！
\end{document}